import { BSTree,TreeNode } from "./00_二叉搜索树BSTree";
import { AVLTreeNode } from "./04_封装AVLTreeNode(左旋转操作)";
class AVLTree<T> extends BSTree<T> {
    // 重写调用createNode 方法
    protected createNode(value: T): TreeNode<T>{

        return new AVLTreeNode(value)
    }

    // 如何去找不平衡的节点
    checkBalance(node:AVLTreeNode<T>,isAdd = true) {
        // 找到要找的节点的父节点
        let current = node.parent;
        // 当节点存在，去判断其是否平衡，不平衡的话则进行旋转操作
        while(current){
            if(!current.isBalanced){
                this.rebalance(current);
                // 这个位置是旋转完成的操作，break决定不会进一步查找父节点是否平衡的情况了
                // 添加的情况是不需要进一步查找的，直接break,因为徐亚转后不影响树的高度没有改变
                // 删除的情况是需要进一步向上查找的不能break
               if(isAdd) break;
            }
            current = current.parent;
        }
    }

    //  如何找到不平衡的节点，先不管?

    // 假设已经找到了,那我们如何将这个节点变平衡
    // root 找到的不平衡的节点 根据不平衡的节点LL/RR/LR/RL让子树平衡
    rebalance(root: AVLTreeNode<T>){
        const pivot = root.higherChild;
        const current = pivot?.higherChild;
        let resultNode: AVLTreeNode<T> | null = null;

        if(pivot?.isLeft){ // L left
            if(current?.isLeft){ // LL left left
                resultNode = root.rightRotation()
            }else{ // LR left right
                pivot.leftRotation()
                // 左旋和右旋都将旋转后的根节点返回出去了，所以这里的resultNode是新的根节点
                resultNode = root.rightRotation()
            }
        }else{// R right
            if(current?.isLeft){ //RL right left
                pivot?.rightRotation();
          
                resultNode = root.leftRotation();
            }else{// RR right right
                resultNode = root.leftRotation();
            }
        }
        // 判断返回的pivot是否有父节点
        if(!resultNode?.parent){
            this.root = resultNode
        }
    }

}

const avlTree = new AVLTree<number>()

// const delMums: number[] = []
// for( let i=0; i<20; i++ ){
//     const randomNum = Math.floor(Math.random()*200)
    
//     // if(i<5){
//     //     delMums.push(randomNum)
//     // }
//     avlTree.insert(randomNum)
// }
// console.log(delMums)
// avlTree.insert(50)
// avlTree.insert(100)
// avlTree.insert(150)

// avlTree.print()


avlTree.insert(50)
avlTree.insert(25)
avlTree.insert(100)
avlTree.insert(150)
avlTree.insert(12)
avlTree.insert(99)
avlTree.insert(154)
avlTree.insert(1544)
avlTree.insert(1895)
avlTree.insert(87)
avlTree.insert(2)


// avlTree.print()

// avlTree.remove(25)

// avlTree.remove(12)

avlTree.print()